package com.ly.algorithm.leetcode.backtracking;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @Classname Problem131
 * @Description
 *
 * 131. 分割回文串
 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 *
 * 返回 s 所有可能的分割方案。
 *
 * 示例:
 *
 * 输入: "aab"
 * 输出:
 * [
 *   ["aa","b"],
 *   ["a","a","b"]
 * ]
 *
 *
 *
 * @Date 2020/12/25 18:29
 * @Author 冷心影翼
 */
public class Problem131 {

	public static void main(String[] args) {
//		System.out.println("123".substring(2));
		Solution131 solution131 = new Solution131();
		System.out.println(solution131.partition("aaba"));
		ArrayList<String> objects = new ArrayList<>();
	}

}


class Solution131 {

	private List<List<String>> res = new ArrayList<>();

	public List<List<String>> partition(String s) {
		backtracking(s,new LinkedList<>());
		return res;
	}

	public void backtracking(String s,LinkedList<String> path) {
		if(s.length() == 0) {
			if(isValid(path)) {
				List<String> copy = new ArrayList<>(path);
				Collections.reverse(copy);
				res.add(new ArrayList<>(copy));
			}
			return;
		}
		for (int i = s.length()-1; i>=0; i--) {
			path.add(s.substring(i));
			backtracking(s.substring(0,i),path);
			path.removeLast();
		}
	}


	private boolean isValid(List<String> path) {
		final boolean[] flag = {true};
		path.forEach(it->{
			for (int i = 0; i < it.length()/2; i++) {
				if(it.charAt(i) != it.charAt(it.length()-i-1)) {
					flag[0] = false;
					break;
				}
			}
		});
		return flag[0];
	}

}